LintCode Solution - String Permutation II | Entry-Level段子手的日常

http://www.lintcode.com/en/problem/string-permutation-ii/

Given a string, find all permutations of it without duplicates.
Example
Given “abb”, return [“abb”, “bab”, “bba”].

Given “aabb”, return [“aabb”, “abab”, “baba”, “bbaa”, “abba”, “baab”].

We can see the keywords in the description of the question is that “find all permutations”. It is easy for us to think that we can use dfs to solve this problem.


public class Solution {
    /**
    * @param str a string
    * @return all permutations
    */
 
    public List<String> stringPermutation2(String str) {
        // Write your code here
        char[] string = str.toCharArray();
        boolean[] isUsed = new boolean[string.length];
        Arrays.sort(string);
        List<String> result = new ArrayList<String>();
        String temp = new String();
        stringPermutation2Helper(result, temp, string, isUsed);
        return result;
    }
    
    private void stringPermutation2Helper(List<String> result, 
                                            String temp,
                                            char[] string,
                                            boolean[] isUsed) {
        if (temp.length() == string.length) {
            result.add(temp);
            return;
        }
        for (int i = 0; i < string.length; i++) {
            if (isUsed[i] == true || i != 0 && 
                isUsed[i - 1] == false && 
                string[i] == string[i - 1]) {
                continue;
            }
            isUsed[i] = true;
            stringPermutation2Helper(result, temp + string[i], string, isUsed);
            // backtracking
            isUsed[i] = false;
        }
    }
}

This is a navie version of solution. It needs extra memory which is O(n), where the n represents the length of the input string, to store the information if this char in string has been added. The time complexity of this algorithm is O(n^2).

If you want to solve this problem without extra memory space, we can use solution used in “Next Permutation”


/**
* 本代码由九章算法编辑提供。没有版权欢迎转发。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，BAT国内班
* - 更多详情请见官方网站：http://www.jiuzhang.com/
*/

public class Solution {

    /**
    * @param str a string
    * @return all permutations
    */
 
    public List<String> stringPermutation2(String str) {
        // Write your code here
        List<String> result = new ArrayList<String>();
        char[] s = str.toCharArray();
        Arrays.sort(s);
        result.add(String.valueOf(s));
        while ((s = nextPermutation(s)) != null) {
            result.add(String.valueOf(s));
        }
        return result;
    }
    
    public char[] nextPermutation(char[] nums) {
        int index = -1;
        for(int i = nums.length -1; i > 0; i--){
            if(nums[i] > nums[i-1]){
                index = i-1;
                break;
            }
        }
        if(index == -1){
            return null;
        }
        for(int i = nums.length -1; i > index; i--){
            if(nums[i] > nums[index]){
                char temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
                break;
            }
        }
        reverse(nums,index+1,nums.length-1);
        return nums;
    }
    
    public void reverse(char[] num, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            char temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
    }
}